// 动态规划 - 核心 5 步：
// 1. 确定状态表示 - 根据 题目要求，经验，发现重复子问题 确定状态表示
// 2. 推导状态转移方程: dp[i] = ?
//    用 之前的状态 或者 之后的状态 推导当前的状态（根据最近一步划分问题）
// 3. 初始化：保证填表时不越界，结合多开数组的技巧
// 4. 确定填表顺序：填写当前状态值的时候，所需状态的值已经计算过了
// 5. 返回值：结合题目要求 + 状态表示

// 经典题目：斐波那契数列模型，路径问题

// 技巧：
// dp[] 表多开一个长度，处理数组越界及初始化复杂的问题
// dp[][] 表多开一行，多开一列
// 结合滚动数组优化 - 注意赋值顺序

// 例题 4：
// 给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
// 降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。
// 在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。
// 具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
//
//        示例 1：
//
//        输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
//        输出：13
//        解释：如图所示，为和最小的两条下降路径
//        示例 2：
//
//        输入：matrix = [[-19,57],[-40,-5]]
//        输出：-59
//        解释：如图所示，为和最小的下降路径
//
//
//        提示：
//
//        n == matrix.length == matrix[i].length
//        1 <= n <= 100
//        -100 <= matrix[i][j] <= 100

// 解题思路：
// dp[i][j]: 到达 i,j 位置的最小路径和
// dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]) + grid[i][j]
// 使用技巧: dp[][] = new int[m + 1][n + 2]
// dp[0][j] = 0
// 1 <= i <= m: dp[i][0] = dp[i][n + 1] = max
// 从上往下填表，每一行从左往右
// 返回 min(dp[m][j])

public class MinFallingPathSum {
    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m + 1][n + 2];

        for(int i = 1; i <= m; i++) {
            dp[i][0] = Integer.MAX_VALUE;
            dp[i][n + 1] = Integer.MAX_VALUE;
        }

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]) + matrix[i - 1][j - 1];
            }
        }

        int ret = Integer.MAX_VALUE;
        for(int j = 1; j <= n; j++){
            ret = Math.min(ret, dp[m][j]);
        }
        return ret;
    }
}
